This invention relates to the field of data compression and in particular to a hardware implementation of an LZW compression algorithm that comprises a plurality of independent, special-purpose cascaded processors.
It is frequently necessary or helpful for large quantities of information to be quickly transmitted over a network using limited bandwidth. Often servers accomplish this task with software compression, whereby the quantity of data that is transferred is reduced. One such software compression algorithm is the LZW algorithm named for the inventors of the algorithm, Lempel, Ziv and Welch.
The LZW algorithm is widely used in industry and government to reduce the amount of storage space needed to store computer data files. The LZW algorithm is also used on low bandwidth data links such as V.42 modems to improve effective bandwidth by reducing the amount of physical (compressed) information transmitted over a communications link required to transfer a much larger amount of logical (uncompressed) information. Typically, the LZW algorithm is implemented in software executed by a single, general-purpose processor that is not optimized for LZW processing. There is a need in the art for an improved implementation of the LZW algorithm.
According to the present invention, the LZW data compression algorithm is implemented in hardware comprising a plurality of special-purpose, cascaded processors coordinated by a managing processor. Each processor includes hardware-embedded control algorithms specific to its specialized function. These algorithms are in the form of state sequences which collectively perform the LZW compression algorithm. At any instant, three processing steps of the LZW algorithm may be performed simultaneously, one step in each of the independent processors. According to one aspect of the invention, separate physical devices are used for certain data structures, enabling simultaneous access to each data structure during processing. In accordance with the invention, the processing overhead required to create an LZW compressed file is significantly reduced in terms of both component cost and computing time.